package com.dream.algoritm;

// 从上到下找到最短路径（n个数字之和最小,n为矩阵的行数），
// 可以从第一行中的任何元素开始，只能往下层走，同时只能走向相邻的节点，
// 例如图中第一排 2 只能走向 第二排的 7、3；第二排的 7 可以走向第三排的 6、2、9
//
// | 5    | 8    | 1    | 2    |
// | 4    | 1    | 7    | 3    |
// | 3    | 6    | 2    | 9    |
//
// Input: [
//     [5, 8, 1, 2],
//     [4, 1, 7, 3],
//     [3, 6, 2, 9]
// ]
// Output: 4

import java.util.*;

public class Test3 {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {5, 8, 1, 2},
                {4, 1, 7, 3},
                {3, 6, 2, 9}
        };

        int row = matrix.length;
        int col = matrix[0].length;
        int[][] cache = new int[row][col];
        for (int j = 0; j < col; j++) {
            cache[row - 1][j] = matrix[row - 1][j];
        }

        for (int i = row - 2 ; i >= 0; i--) {
            for (int j = 0; j < col; j++) {
                int r1 = j - 1 >= 0 ? cache[i + 1][j - 1] : Integer.MAX_VALUE;
                int r2 = cache[i + 1][j];
                int r3 = j + 1 < col ? cache[i + 1][j + 1] : Integer.MAX_VALUE;
                cache[i][j] = matrix[i][j] + Math.min(r3, Math.min(r1, r2));
            }
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < matrix[0].length; i++) {
            min = Math.min(cache[0][i], min);
        }

        System.out.println(min);
    }

    public static int process(int[][] matrix, int x, int y) {
        // base case
        if (y < 0 || y >= matrix[0].length) {
            return Integer.MAX_VALUE;
        }
        if (x == matrix.length - 1) {
            return matrix[x][y];
        }
        int r1 = process(matrix, x + 1, y - 1);
        int r2 = process(matrix, x + 1, y);
        int r3 = process(matrix, x + 1, y + 1);

        int res = matrix[x][y] + Math.min(r3, Math.min(r1, r2));

        return res;
    }

    public static int process2(int[][] matrix, int x, int y, int[][] cache) {
        // base case
        if (y < 0 || y >= matrix[0].length) {
            return Integer.MAX_VALUE;
        }
        if (x == matrix.length - 1) {
            return matrix[x][y];
        }
        if (cache[x][y] != -1) {
            return cache[x][y];
        }
        int res;
        int r1 = process2(matrix, x + 1, y - 1, cache);
        int r2 = process2(matrix, x + 1, y, cache);
        int r3 = process2(matrix, x + 1, y + 1, cache);

        res = matrix[x][y] + Math.min(r3, Math.min(r1, r2));

        cache[x][y] = res;

        return res;
    }
}
